Source code is typically written by a programmer in a language that attempts to describe a solution to a problem. A compiler is used to process and convert source code to object code that a computer understands. Generally, the compiler reads the source code and builds object code as a collection of binary number instructions. Instruction selection is one of the main tasks of optimizing compilers. Instruction selection can be as simple as selecting a single instruction to encode a single operation. Moreover, instruction selection can be as complex as selecting a pre-defined assembly-level algorithm to encode a recognized source-level algorithm.
Switch statements are one of the main building blocks for implementing state transition automata. An end user typically writes a description of an automaton. The actual code (e.g. “C”, “C++”, etc.) for the automation can be generated by a program generator for example. The generated code typically shows a certain structure and often lacks the elegance of the end user's written code. An example of user-written code including a switch statement having a number of case labels is shown below.
extern voiddispatch(int x, enum e_tag tag) { switch (tag) {  case e_1:   process_1(x);   break;  case e_3:   process_3(x);   break;  case e_5:   process_5(x);   break;  case e_7:   process_7(x);   break;  case e_9:   process_9(x);   break; }
Conventional encoding techniques are not proficient at recognizing distances between values (herein referred to as “strides”) when encoding switch statements and other code. A conventional technique that does not recognize stride values generates an s-times (where “s” is the stride length) bigger branch table filling the gaps with branches to the default block (usually done for stride length=2). A conventional encoding technique for encoding the switch statement above is shown below.
ldr r3, #branch_table
sub r2, r1, #1
cmp r2, #8
bhi L1.default
ldr r3, [r3, r2]
add pc, pc, r3
The resulting branch_table:                .word L1.process—1        .word L1.default        .word L1.process—3        .word L1.default        .word L1.process—5        .word L1.default        .word L1.process—7        .word L1.default        .word L1.process—9        
As shown above, the branch table uses “default” to fill in gaps between stride values. This is expensive and inefficient. Correspondingly, the conventional encoding technique shown above is not efficient at encoding the range and stride check for a given range m, m+s, m+2s, . . . , m+ns, where “m” is the minimum start value of the range, “s” is the stride length (constant distance between values) of a stride, and “n” is the number of strides. Typically, three tests are required to determine whether a variable (e.g. “x”) is inside a range. The three tests are:x>=m  (1)x<=m+ns  (2)x=m(mod s)  (3)
As seen above, the conventional encoding technique requires at least three compares and, more significantly, three conditional branches. The three conditional branches use up precious space in the branch target buffer. Additionally, the conditional branches are subject to misprediction which can result in a potentially expensive range check. Branch misprediction occurs when a computing system mispredicts the next instruction to process in branch prediction. Branch prediction is important since delivering high branch-prediction rates advances performance gains in high-performance computing.